Kai-Min Chung
Abstract:
How do we test if a weather forecaster actually knows something about whether it will rain or not? Can we distinguish a ``charlatan'' from a true expert? Can we evaluate whether a scientific theory actually predicts some physical phenomenon?
Intuitively, a ``good'' forecast test should be *complete*---namely, a forecaster knowing the distribution of Nature should be able to pass the test with high probability, and *sound*---an uninformed forecaster should only be able to pass the test with small probability.
In this talk, we present a comprehensive complexity-theoretic study of the feasibility of sound and complete forecast testing, introducing various notions of both completeness and soundness, inspired by the literature on interactive proofs. Our main result is an incompleteness theorem for our most basic notion of computational sound and complete forecast testing: If Nature is implemented by a polynomial-time algorithm, then every complete polynomial-time test can be passed by a completely uninformed polynomial-time forecaster with high probability.
We will additionally discuss alternative notions of soundness and completeness and present both positive and negative results for these notions.
Joint work with Edward Lui and Rafael Pass.